class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
      int len = stones.size();
      int sum = 0;
      int cnt = 0;
      for(int i = 0;i < len;i++){
        sum += stones[i];
      }
      cnt = sum;
      sum /= 2;
      vector<int> dp(sum+1,0);
      for(int i = 0;i < len;i++){
        for(int j = sum;j >= 0;j--){
          if(j >= stones[i]){
            dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
          }
        }
      }
       int index = cnt - dp[sum]*2;
      return index;
    }
};
